package arraylist

import (
	"06-GenericsTest/lists"
	"06-GenericsTest/utils"
	"fmt"
	"slices"
	"strings"
)

// 断言 List 实现接口 lists.List
var _ lists.List[int] = (*List[int])(nil)

// List 链表结构
type List[T comparable] struct {
	elements []T
	size     int
}

const (
	growthFactor = float32(2.0)  // 扩容因子
	shrinkFactor = float32(0.25) // 缩容因子
)

// New 创建链表
func New[T comparable](values ...T) *List[T] {
	list := &List[T]{}
	if len(values) > 0 {
		list.Add(values...)
	}
	return list
}

// Add 向链表末尾添加元素
func (l *List[T]) Add(values ...T) {
	l.growBy(len(values))
	for _, value := range values {
		l.elements[l.size] = value
		l.size++
	}
}

// Get 获取下标 index 的元素
func (l *List[T]) Get(index int) (T, bool) {
	if !l.withinRange(index) {
		var t T
		return t, false
	}
	return l.elements[index], true
}

// Remove 移除下标 index 的元素
func (l *List[T]) Remove(index int) {
	if !l.withinRange(index) {
		return
	}
	clear(l.elements[index : index+1])
	copy(l.elements[index:], l.elements[index+1:l.size])
	l.size--

	l.shrink()
}

// Contains 判断是否包含元素
func (l *List[T]) Contains(values ...T) bool {
	for _, searchValue := range values {
		found := false
		for i := 0; i < l.size; i++ {
			if l.elements[i] == searchValue {
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}
	return true
}

// Values 获取链表元素切片
func (l *List[T]) Values() []T {
	newElements := make([]T, l.size, l.size)
	copy(newElements, l.elements[:l.size])
	return newElements
}

// IndexOf 获取元素所在下标
func (l *List[T]) IndexOf(value T) int {
	if l.size == 0 {
		return -1
	}
	for index, element := range l.elements {
		if element == value {
			return index
		}
	}
	return -1
}

// Empty 判断链表为空
func (l *List[T]) Empty() bool {
	return l.size == 0
}

// Size 获取元素个数
func (l *List[T]) Size() int {
	return l.size
}

// Clear 清空链表
func (l *List[T]) Clear() {
	l.size = 0
	l.elements = []T{}
}

// Sort 链表元素排序
func (l List[T]) Sort(comparator utils.Comparator[T]) {
	if len(l.elements) < 2 {
		return
	}
	slices.SortFunc(l.elements[:l.size], comparator)
}

// Swap 交换两个元素
func (l *List[T]) Swap(i, j int) {
	if l.withinRange(i) && l.withinRange(j) {
		l.elements[i], l.elements[j] = l.elements[j], l.elements[i]
	}
}

// Insert 指定位置插入
func (l *List[T]) Insert(index int, values ...T) {
	if !l.withinRange(index) {
		if index == l.size {
			l.Add(values...)
		}
		return
	}
	length := len(values)
	l.growBy(length)
	l.size += length
	copy(l.elements[index+length:], l.elements[index:l.size-length])
	copy(l.elements[index:], values)
}

// Set 指定位置设置元素
func (l *List[T]) Set(index int, value T) {
	if !l.withinRange(index) {
		if index == l.size {
			l.Add(value)
		}
		return
	}
	l.elements[index] = value
}

// String 字符串显示链表
func (l *List[T]) String() string {
	str := "ArrayList: "
	values := make([]string, 0, l.size)
	for _, value := range l.elements[:l.size] {
		values = append(values, fmt.Sprintf("%v", value))
	}
	str += "[" + strings.Join(values, ", ") + "]"
	return str
}

// withinRange 判断是否越界
func (l *List[T]) withinRange(index int) bool {
	return index >= 0 && index < l.size
}

// resize 链表底层切片重新分配地址
func (l *List[T]) resize(cap int) {
	newElements := make([]T, cap)
	copy(newElements, l.elements)
	l.elements = newElements
}

// growBy 判断是否增加 n 各元素需要扩容
func (l *List[T]) growBy(n int) {
	currentCapacity := cap(l.elements)
	if l.size+n >= currentCapacity {
		newCapacity := int(growthFactor * float32(currentCapacity+n))
		l.resize(newCapacity)
	}
}

// shrink 缩容
func (l *List[T]) shrink() {
	if shrinkFactor == 0.0 {
		return
	}
	currentCapacity := cap(l.elements)
	if l.size <= int(float32(currentCapacity)*shrinkFactor) {
		l.resize(l.size)
	}
}
